/**
 *  Insertion Sort
 *
 *  Time complexity: 0 + 1 + 2 + ... + (n - 1) = n * (n - 1) / 2 = O(n^2)
 *  Space complexity: O(1)
 */


import java.util.Arrays;

class InsertionSort<E extends Comparable<E>> {

    public void sort(E[] arr) {
        int N = arr.length;
        
        // Sanity check
        if (N < 2) {
            return;
        }

        for (int i = 1; i < N; i++) { // Outter loop, check a[1] to a[N - 1]
            for (int j = i; j > 0; j--) { // Inner loop, put small number to the front
                if (arr[j].compareTo(arr[j - 1]) < 0) {
                    swap(arr, j, j - 1);
                }
            }
        }
    }

    private void swap(E[] arr, int i, int j) {
        E tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}
